【题解】 [AHOI2013]差异 后缀自动机.SAM luoguP4248 | Qiuly's blog!

【题解】 [AHOI2013]差异 后缀自动机.SAM luoguP4248

Posted on | In | Comments:

刚开始发现 $SA$ 很可做，不过当时没有看范围，心想美滋滋了这个就是 $SA$ 的板子，然后一看范围心就凉了。

不过可以用 $SAM$ ，我们知道，对于两个串，它们的最长公共子串就是它们在前缀树上的 $Lca$ 。这是显然的，不明白的同学可以康康 $Qiuly$ 酱之前写的 $SAM$ ，可以观察观察图片。

我们观察式子，发现 $\sum_{1\leq i<j\leq n} len(T_i)+len(T_j)$ 是等于 $\frac{(n-1)\times n\times(n+1)}{2}$ 的，这个可以 $O(1)$ 算出。

那么 $2\times lcp(T_i,T_j)$ 怎么求呢？

那么对于一个结点 $x$ ，我们依次统计 $x$ 的儿子，并依次更新 $x$ 的 $size$ ，对于一个 $x$ 的儿子 $y$ ，枚举的时候它对答案的贡献显然是 $size[x]\times len[x]\times size[y]$ ，因为 $y$ 的子树中的任意一结点(包括 $y$ ) ，与 $x$ 之前枚举过的所有儿子的子树中的所有结点的 $Lca$ 都是 $x$ 。并且对于一个 $x$ ，它所造成的贡献就是 $Len[x]$ 。

最后统计出来的答案再乘上 $2$ 就是后面那个式子啦~\(≧▽≦)/~ 。

不过要注意一点，后缀自动机是会复制结点的，这些复制的结点不属于原串因此不能计算贡献。

然后就是代码的问题了。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1e6+7;
struct SAM {
    int last,cnt;
    int ch[N][26],fa[N],len[N],sz[N],hep[N],tot[N];
    SAM() {last=cnt=1;}
    inline void ins(int c) {
        int p=last,np=++cnt;
        last=np,len[np]=len[p]+1,sz[np]=1;
        while(p&&!ch[p][c]) ch[p][c]=np,p=fa[p];
        if(!p)fa[np]=1;
        else {
            int q=ch[p][c];
            if(len[q]==len[p]+1)fa[np]=q;
            else {
                int nq=++cnt;len[nq]=len[p]+1;
                memcpy(ch[nq],ch[q],sizeof(ch[q]));
                fa[nq]=fa[q],fa[q]=fa[np]=nq;
                while(p&&ch[p][c]==q) ch[p][c]=nq,p=fa[p];
            }
        }return;
    }
    inline ll calc() {
        ll res=0;
        for(int i=1;i<=cnt;++i) hep[len[i]]++;
        for(int i=1;i<=cnt;++i) hep[i]+=hep[i-1];
        for(int i=1;i<=cnt;++i) tot[hep[len[i]]--]=i;
        for(int i=cnt;i>=1;--i) {
            int node=tot[i];
            res+=(ll)sz[fa[node]]*sz[node]*len[fa[node]];
            sz[fa[node]]+=sz[node];
        }return res;
    }
}T;
char s[N];
int main() {
    scanf("%s",s);
    int n=strlen(s);
    for(int i=0;i<n;++i)T.ins(s[i]-'a');
    printf("%lld\n",(ll)(n-1)*n*(n+1)/2-2*T.calc());
    return 0;
}

本文标题:【题解】 [AHOI2013]差异 后缀自动机.SAM luoguP4248

文章作者:Qiuly

发布时间:2019年03月30日 - 00:00

最后更新:2019年03月30日 - 15:38

原始链接:http://qiulyblog.github.io/2019/03/30/[题解]luoguP4248/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。